/**
 * 快速排序（Quick Sort）是一种高效的排序算法，采用分治策略来对一个数组进行排序。以下是其基本步骤：
 * - 选择基准值：从数组中挑选一个元素作为“基准”（pivot）。
 * - 分区操作：重新排列数组，使得所有比基准小的元素都排在基准的前面，所有比基准大的元素都排在基准的后面。这个过程称为分区（partition）操作。
 * - 递归排序子数组：递归地将小于基准值的子数组和大于基准值的子数组进行快速排序。
 * 快速排序的特点
 * - 时间复杂度：平均情况下为 O(n log n)，最坏情况下为 O(n^2)。
 * - 空间复杂度：O(log n)，因为递归调用栈会占用额外的空间。
 * - 稳定性：不是稳定的排序算法，相同元素的相对位置可能会改变。
 */

const arr1 = [5, 7, 1, 6, 8, 2, 3, 9, 4];
const arr2 = [5, 7, 1, 6, 8, 2, 3, 9, 4];

/**
 * 简单快速排序(简单快排会创建新的数组)
 * @param arr 要排序的数组
 * @param mode 排序的模式(true:正序 false:倒序)
 * @returns 排序后的数组
 */
function quickSort(arr, mode = true) {
  if (arr == null || arr.length == 0) return arr;
  let leader = arr[0];
  let left = [];
  let right = [];
  for (let i = 1; i < arr.length; i++) {
    const _mode = mode ? arr[i] < leader : arr[i] > leader;
    if (_mode) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return [...quickSort(left, mode), leader, ...quickSort(right, mode)];
}

let zx = quickSort(arr1);
console.log("▶『正序』", zx);
let dx = quickSort(arr2, false);
console.log("▶『倒序』", dx);
